import net.egork.utils.Solver;
import net.egork.utils.io.InputReader;

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;

public class ROADS implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {

        int k = in.readInt();
        int n = in.readInt();
        int r = in.readInt();

        int v[] = new int[n];
        Arrays.fill(v, -1);
        Edge e[] = new Edge[r];

        int eu;
        for (int i = 0; i < r; ++i) {
            e[i] = new Edge();
            eu = in.readInt() - 1;
            e[i].v = in.readInt() - 1;
            e[i].len = in.readInt();
            e[i].cost = in.readInt();
            e[i].next = v[eu];
            v[eu] = i;
        }

        int minLen[] = new int[n];
        Arrays.fill(minLen, Integer.MAX_VALUE);
        minLen[0] = 0;
        int minCost[] = new int[n];
        Arrays.fill(minCost, Integer.MAX_VALUE);
        minCost[0] = 0;

        Node temp = new Node(0, 0, 0);
        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        pq.add(temp);
        while (!pq.isEmpty()) {
            temp = pq.poll();
            if (temp.u == n - 1) {
                out.println(temp.len);
                return;
            }
            for (int u = v[temp.u]; u != -1; u = e[u].next) {
                Node ne = new Node(e[u].v, temp.len + e[u].len, temp.cost + e[u].cost);
                if (ne.cost <= k && (ne.len < minLen[ne.u] || ne.cost < minCost[ne.u])) {
                    pq.add(ne);
                    minLen[ne.u] = ne.len;
                    minCost[ne.u] = ne.cost;
                }
            }
        }
        out.println(-1);
    }

    class Edge {
        public int v, len, cost, next;
    }

    class Node implements Comparable<Node> {
        public int u, len, cost;

        public Node(int u, int len, int cost) {
            this.u = u;
            this.len = len;
            this.cost = cost;
        }

        public int compareTo(Node o) {
            return this.len - o.len;
        }
    }
}

